﻿using Enyim;
using Microsoft.AspNetCore.DataProtection.KeyManagement;
using MongoDB.Driver;
using Org.BouncyCastle.Math.EC.Rfc7748;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace NetCore6ConsoleTestOne
{
    public class 城市映急面试题
    {
        #region 给出任意正整数X（X 小于 2的31次幂）, 求不比X小且是2的整数次幂中最小的值Y。例如X=7，则Y为8；X=8，则Y为8。

        /// <summary>
        /// 
        /// </summary>
        /// <param name="x">x<2^31</param>
        public static void MinY(int x) {
            Double[] list = new Double[31];
            for (var i = 0; i < 31; i++)
            {
                list[i] = Math.Pow(2, i + 1);
            }
            for (var i = 0; i < 31; i++)
            {
                if (x <= list[i])
                {
                    Console.WriteLine($"{x}输出{list[i]}");
                    return;
                }
            }
            Console.WriteLine($"数字大于2的31次幂");
        }
        #endregion

        #region 
        /// <summary>
        /// 开方
        /// </summary>
        /// <param name="a">开方数:2</param>
        /// <param name="b">开方次数:1000</param>
        public static void TestSqrt(int a, int b) {
            Console.WriteLine($"{Convert.ToString(Math.Pow(a,b))}");
            return;
            List<int> rt = new List<int>() { a };
            for (var i = 0; i < b - 1; i++)
            {
                //开方
                int lt = rt.Count;
                for (var j = lt - 1; j >= 0; j--)
                {
                    rt[j] = rt[j] * a;
                    if (rt[j] >= 10)
                    {
                        jinwei(rt, rt[j], j);
                        rt[j] = rt[j] % 10;
                    }
                }
            }
            rt.Reverse();
            Console.WriteLine($"自定义函数开方:{string.Join("",rt)}");
        }

        /// <summary>
        /// 进位处理
        /// </summary>
        /// <param name="rt"></param>
        /// <param name="tt">进位的数</param>
        /// <param name="index">进位的当前索引</param>
        public static void jinwei(List<int> rt,int tt,int index)
        {
            if (index + 1 >= rt.Count)//如果是最大位数，就扩容
            {
                rt.Add(tt / 10);
            }
            else
            {
                rt[index + 1] = rt[index + 1] + tt / 10;
                if (rt[index + 1] >= 10)
                {
                    jinwei(rt, rt[index + 1], index + 1);
                    rt[index + 1] = rt[index + 1] % 10;
                }
            }
        }


        public static void MathSqrt(int a, int b) {
            Console.WriteLine($"Math开方：{Math.Pow(a, b)}");
        }
        #endregion

        #region 有一个数组 a[1000]存放了1000 个整数，这 1000个数都大于等于1，小于等于999, 并且只有两个数是相同的,剩下的 998个数均不相同。请写一个最优搜索算法，找出相同的那个数的值，并给出该算法的时间复杂度。
        /// <summary>
        /// Array1000中找重复的
        /// </summary>
        public static void FindRepeat()
        {
            //生成1000的数组
            int[] dataList = CreateArray1000();
            Dictionary<int, int> dict = new Dictionary<int, int>();
            for (var i = 0; i < dataList.Length; i++)
            {
                //初始化dic
                dict[dataList[i]] = 0;
            }

            //时间复杂度决定于这块，也就是dataList.Length
            for (int i = 0; i < dataList.Length; i++)
            {
                int key = dataList[i];
                if (dict[key] == 1)
                {
                    Console.WriteLine($"重复数字{key}");
                }

                dict[key] = 1;
            }
            Console.ReadLine();
        }

        public static void FindRepeat(int[] dataList)
        {
            int tortoise = dataList[0];
            int hare = dataList[0];
            do
            {
                tortoise = dataList[tortoise];
                hare = dataList[dataList[hare]];
            } while (tortoise != hare);


            int ptr1 = dataList[0];
            int ptr2 = tortoise;
            while (ptr1 != ptr2)
            {
                ptr1 = dataList[ptr1];
                ptr2 = dataList[ptr2];
            }

            Console.WriteLine($"重复数字{ptr1}");
            Console.ReadLine();
        }

        /// <summary>
        /// 生成1000数组
        /// </summary>
        /// <returns></returns>
        public static int[] CreateArray1000()
        {
            int[] arr = new int[1000];
            for (var i = 1; i < 1000; i++)
            {
                arr[i - 1] = i;
            }
            arr[999] = 3;
            return arr;
        }
        #endregion
    }
}
